Algorithms: Design and Analysis Part1

53hours, 6weeksぐらいで終えるボリューム (公式)

57.5hours in 3 weeksかかった

感想

日本語字幕がある講座とない講座がある

各国語の字幕は有志が付けている

Week 1

Union-Find

Set of algorithms: Quick Find, Quick Union

dynamic connectivity problemを解くためのアルゴリズム

dynamic connectivity problem

N個のobjectsと、それらを結ぶ辺が与えられたとき、object i, j は繋がっているか

直接でも間接でも辺によって繋がっていればよい

現実世界での応用

Pixels in a digital photo.

Computers in a network.

Friends in a social network.

Transistors in a computer chip.

Elements in a mathematical set.

Variable names in Fortran program.

Metallic sites in a composite system.

programmingではobjectsには0 through Nの名前を付けることになる

it's useful to use it as an index

objectsの情報は不要なのでindexだけで十分なことがほとんど

UF

Set

Quick Findの実装

code:java

public class QuickFindUF {

private int[] id;

public QuickFindUF(int N) {

for (int i = 0; i < N; i++) {

}

}

public boolean connected(int p, int q) {

}

public void union(int p, int q) {

for (int i = 0; i < id.length; i++) {

}

}

}

}

考察

treeはフラットだけど維持するコストが高い

こんにちのような大量のデータを前にしては使い物にならない

Quick Union

Quick Findと比較して

より高速なアプローチ

同じデータ構造を用いる

lazy approach

unionの操作で木を構築していく

union(int p, int q)

q, pそれぞれのroot同士をくっつける

indexとデータが一致している要素はroot

code:java

public class QuickUnionUF {

private int[] id;

public QuickUnionUF(int N) {

for (int i = 0; i < N; i++) {

}

}

private int root(int i) {

return i;

}

public boolean connected(int p, int q) {

return root(p) == root(q);

}

public void union(int p, int q) {

int i = root(p);

int j = root(q);

}

}

考察

treeが高くなりがち

connectedが遅い

早くなってない、むしろ遅くなっている

Weighted Quick Union

木の構築に一手間かける

高さの低い木を高い木のrootに付けるよう選択することで高さを抑えることができる

高さを抑えると当然探索コストが減る

重み付けを深さでなく要素のsizeなどで行うこともできる

code:java

public void union(int p, int q) {

int i = root(p);

int j = root(q);

if (i == j) return;

} else {

}

}

考察

木の深さは高々 log N になる

Path comression

一度構築された木を圧縮する

最終的に木はほぼフラットになる

code:java

private int root(int i) {

}

return i;

}

やらない手はない

Summary

定数時間でこの問題を解くことはできない

10億要素が与えれて10億操作をする場合にQuick Findでは30年かかるところを最終形では6秒で解くことができる

これがアルゴリズムの力

大事なのは、いかにcomputerの処理が早かろうと関係ないということ

Interview Questions: Union–Find (ungraded)

Social network connectivity

n人のmember

m個のtimestamps、member同士がfriendになった時間を表す

最も速い時間を求めるアルゴリズムを考えよ

component内の最大値を求める

Assignment: Percolation

n * n の grid の最上部rowから最下部のrowまで繋がっているcomponentが存在するとき、percolates という

percolationは抽象化したモデルであり，現実世界では絶縁体と導体であったりする

20 * 20 = 400 sites を blocked で初期化する

blocked sites から random に選び、これを open する

最上位rowのopen siteと繋がっていれば full site となる

最下位rowののいずれかが full site となればpercalated

この試行をT回繰り返す

Tが十分に大きい（例えば、少なくとも30）と仮定すると、95％信頼区間を提供可能

virtual sitesを使うのを見落としていた

提出すると自動で採点される

コードスタイルなどはチェックされるが減点対象にはならない

code:shell

$ spotbugs *.class

$ pmd .

$ checkstyle *.java

Memory complexity

Time complexity

実行時間だけでなく、特定のメソッドを呼んだ回数など

Correctness

仕様通りにpublic APIを実装している

Errorの定義なども見る

virtual sitesを使うことでbackwashが起きる問題への対応

わからなくて諦めた

関連

Analysis of algorithms

programmerがperformance characteristicsを理解していないせいで苦しむ顧客がいる、というのをこんにちよく見かける

アルゴリズムによる成功例

FFT algorithm

Discrete Fourier transform

DVD, JPEG, MRI etc.

Bruto forceでN^2のところをN log Nにした

N-body simulation

Barnes-Hut algorithm

Bruto forceでN^2のところをN log Nにした

これまでに不可能だった研究をできるようにした

科学的手法によってperformanceを分析することができる

観察、仮設、予測、検証

原則

実験は再現可能性がなければならない

仮設は反証可能でなければならない

System independent effects

アルゴリズム

入力データ

System dependent effects

Hardware: CPU, Memory, cache...

Software: compiler, interpreter, GC...

System: OS, network, other apps...

Three-sum問題

だいぶまし

最悪計算量を考える

要求によって最善は異なるがアプローチは2つ

最悪のケースに対応できるアルゴリズムを選択する

ランダムなデータにおおむね対応できるアルゴリズムを選択する

Big Theta

Big Oh

Big Omega

入力の特性を理解し、その入力に対して効率的なアルゴリズムを見つけることに焦点を当てるべき

本当に性能を予測したりアルゴリズムを比較したりするためには、定数の範囲内ではなく、より詳細な分析を行う必要がある

多くの人が、問題の難易度の改善された上限値を与えるとされるBig Ohの結果を、実行時間の近似モデルとして解釈してしまう

このコースでは，近似モデルに焦点を当てて，チルダ表記を使う

Week 2

Stackの実装

linked list

backing array

resizingの問題がある

push(x)

pushごとに1つずつと ~N^2 / 2

倍々で拡張していくrepeated doublingアプローチだと ~log M

pop()

doublingの逆だからと1/2 * lengthになったらshrinkすれば良いと思ったら間違い

pop (halve) -> push (double) -> pop -> push を境界で繰り返すと高コスト

1/4まで減ったら1/2にshrinkiするのが適切

Java

Stackの実用例

Parsing in a compiler.

Java virtual machine.

Undo in a word processor.

Back button in a Web browser.

PostScript language for printers.

Implementing function calls in a compiler.

関数呼び出しではlocal environmentとreturn addressをわたす (push)

Dijkstra's two stack algorithm

value stackとoperator stackの2つで式を評価する

Job interview

Stack2つを組み合わせてQueueを作る

最大値を定数時間で返せるStackを実装せよ

Javaの配列でGenericsができないのはなぜか

Assignment: Queues

Elementary sort

どんなdata typeでもsortできる仕組みとは

itemがcomparableであればよい

Selection sort

N^2

Intersion sort

Shell sort

Shuffling

簡易シャッフルの実装は簡単だがbugが混入することも

Best practices for shuffling

Continuously monitor statistic properties: hardware random-number generators are fragile and fail silently.

Use an unbiased shuffling algorithm.

Convex Hull

点の集合があった時に線を引く事でそれらを全て囲むような最小の点集合を求める問題

Week 3

Merge sort

insertion sortと比べて圧倒的高速

ふつうのcomputerでは 10^8 / second

super computerでも 10^12 / second

アルゴリズムの力が圧倒的に強い

Sorting compelixty

アルゴリズムのcomplexityを見るときに最悪ケース (upper bound) と最善ケース (lower bound) を考える

decision treeの高さがupper boundとなる

Comparator

プリミティブ型でないデータをソートする場合、複数のソート方法が考えられる

例えば生徒のリストがあったときに学年でソートしたり名前でソートしたり

Comparable interfaceを実装しているStudent classのcompareToでなく、ソート条件ごとのComparatorを用意することでデータ型の定義とソート処理ロジックの分離を行える

Stability

安定ソートの問題

安定ソートはinsertion sort

merge sortもmerge処理が安定性を持つように書かれているなら安定

非安定ソートはselection sort, shell sort

大事なのはアプリケーションの性質として安定性が求められるのかどうかを判断し、適切なソートを選べること

Assignment: Collinear Points

平面内にあるn個の点から4つ以上の点を接続するすべての線分を見つける

Bruto forceでまず解いて、次に高速なアルゴリズムを書く

安定ソートでないと実現できない

Quick sort

21世紀の最も重要なアルゴリズムの10に数えられる

Merge sortに比べてのメリット

In-placeで実装ができる

ただし実装はやや複雑になる

メモリを使ってよいのであれば補助配列を使って簡潔に書ける

速い

ランダムであれば比較処理の回数の期待値は1.39 NlogN

Merge sortより39%多いがデータ操作は少ないので速い

最悪はN^2だがランダムシャッフルでそうなることは天文学的確率なので無視できる

非安定ソート

分割処理の際に要素を交換するが同値のどちらを取るかは未定なので安定ソートにならない

ただし補助配列を使って安定ソートにする実装もある

高速化

さらなる高速化を実現した実装もある

Selection

配列の中からk番目に大きい値を探す

Quick sortと似たQuick selectというアルゴリズムでは線形時間で完了できる

Duplicate keys

sortするデータに重複するキーが入っていたら？

Merge sortは影響を受けない

Quick sortはN^2に近づく

Dijkstra's 3-way partitioningにより、重複するデータを検査せずに分割を完了することができる

System sorts

Week 4

Priority queue

stack, queueと違い、追加順ではなく最小または最大の要素をremoveする

現実世界の応用

Event-driven simulation. customers in a line, colliding particles

Numerical computation. reducing roundoff error

Data compression. Huffman codes

Graph searching. Dijkstra's algorithm, Prim's algorithm

Number theory. sum of powers

Artificial intelligence. A* search

Statistics. maintain largest M values in a sequence

Operating systems. load balancing, interrupt handling

Discrete optimization. bin packing, scheduling

Spam filtering. Bayesian spam filter

ストリーミング入力にも使える

N個の要素を持つPQからlagest M個を取り出す計算量

いくつかの実装がある

いずれもspace complexityはM

elementary

愚直に毎回最小最大を探す場合はNM

binary heap

NlogM

best in theory

N

実装

unordered array

stack, queue同様にデータをただ配列の末尾に足すだけ

insertはO(1)だが最大を取るのにO(N)

ordered array

内部に配列を持ってデータを管理する

データ追加時にsortする

insertはO(N)だが最大を取るのにO(1)

binary heap

insert O(logN), del max O(logN)

Binary heap

perfectly balanced except for bottom level

木の高さはlogN

配列で表現できる

max-oriented binary treeの場合はparentの値はchildより必ず大きい

childの値が大きくなったら、条件を満たすまでparentとchildを交換する (swim up: 浮上)

max value == root を取り除くには

rootと配列の最後を交換

配列の最後 == 元rootを取り除く

rootをchildと交換して木を調整する (sink: 沈降)

改良

d-array heap

二分ではなくd個に分割する

insert O(logdN), del max O(dlogdN)

Fibonacchi heap

insert O(1), del max O(logN) (amortized)

前提

PQに存在するkeyは変更されない

keys should be immutable

Heap sort

binary heapを使ったsort

in-place

配列でmax-heapを構築する

bottom (array.last) から順にswim up or sinkしていく

最大値から順に決定していく

NlogNでin-place sortができる

Merge sortでは追加のメモリが必要

Quick sortでは最悪N^2

どちらも改良版では実現できるが複雑な実装になる

だがさほど使われない

内側のloopがquick sortより長い

メモリキャッシュの使い方

巨大な配列の場合、メモリへの参照があちこちにある

ツリーを下っていくときに現在参照しているところから遠く離れたメモリアドレスを見ようとするので動作が遅くなることがある

Quick sortはローカル参照を持ち、先ほど参照したものの近くにあるものを常に参照するので大きなブロックがメモリに入ってきても余分なコストがかからない

非安定

Event driven simulation

N個の粒子が平面上を移動する物理シミュレーション

粒子の衝突予測と衝突イベントの処理でPriority queueを使う

Assignment: 8 Puzzle

「アルゴリズム 8 puzzle」で検索するといろんな大学の課題が見つかるので有名ぽい

終了条件が間違っていた。priority queue使っていて最短が先に見つかるのに後続も探索してた

一手前以外は過去に出現した局面かどうかを判定する必要はなかった

局面に至る手数でpriority付けているので、手数が増えて同じ局面の場合は探索ノードにならない

ただのBFS -> priority queueで手数を考慮 -> A* algorithmでヒューリスティック関数を導入

それぞれ計算量が劇的に違う

「現時点までの距離」g

Simbol tables

key value pairの抽象

Hash tableとかを使ったことあればだいたい理解できる特色

elementary implementation

unordered Linked-list

search, insertに最悪Nの計算

ordered array + binary search

search logN

insert N

Binary Search Tree

定義

二分木

symmetric order

larger than left

less than right

Java 実装

key, value, left, rightを持つNode

API

min

tree's left most

max

tree's right most

floor: the smallest key larger than k

ceil: the largest key less than k

rank: how many keys < k?

subtree countを各nodeが持っていれば

Inorder traversal

tree's left mostから辿るだけ

深さ優先探索 DFS してqueueに突っ込めば良い

maxから辿る場合はstackへ

これらの操作のコストはtreeのheightぶんだけで済む

Deletion

木の再構築を行わなくて済む

dynamicな操作が増えると未使用のnodeだらけになりメモリ効率も探索効率も下がる

Hibbard deletion

0 children node

parentからの参照を消すだけ

1 children node

parentからの参照を片方のchildに移すだけ

2 children node

消すkeyの次の値を見つけ、succsessorにする

succsessor nodeにchildrenを付け替える

succsessor nodeのchildrenも付け替える

課題

randomに追加削除を繰り返すと木はバランスを欠いていく

木の高さは√Nになる

この問題に対応するのが次に紹介する赤黒木

計算量

search, insert, deleteがNで実行できることが保証される

search, insertが1.39logN、deleteが√Nで平均的には実行できる

Week 5

BSTの操作をすべてlogNで出来ることを目指す

現実問題に対応できるようなデータ構造を目指す

実際のアプリケーションではランダムではなく偏りがあることが多い

2−3 Search Trees

BSTを汎化したもの

2-node

1 key, 2 children

BSTと同じ

3-node

2 key, 3 children

smaller key, greater keyがある

left childはsmaller keyより小さいkeyを持つsubtree

right childはsmaller keyより大きいkeyを持つsubtree

middle childはsmaller keyとgreater keyの間のkeyを持つsubtree

rootから末端 (null) までの距離がすべて等しい完全平衡木

performance

logarithmic perfomanceを保証できる

worst case: すべてが2-nodeだと木の高さがlgN

best case: すべてが3-nodeだと木の高さがlog3N≒0.631lgN

1 million nodesでも12~20

1 billion nodesでも18~30

ただし実装は複雑になる

Red-Black BSTs

BSTに少しコードを足すだけで2-3 Treeを実現できるデータ構造

off topic

1979にSedgewick先生が論文を書いた

当時完全に理解したと思ったが、このコースの中で2007にさらに改良された実装を見つけた

But just a few years ago for this course I found a much simpler implementation of red-black trees and this is just the a case study showing that there are simple algorithms still out there waiting to be discovered and this is one of them that we're going to talk about.

Left-leaning red-black BSTs

以下の特色を備えたBST

node間のlinkにred link, black linkを設ける

実装としてはnodeにcolor of parent linkを持たせる

black linkは通常の参照

red link

2-3 treeにおける3-nodeでは同一nodeで扱われるkeyを示す

node追加時はredとして追加し、leftにしか存在しないように調整する

rootから末端 (null) までのblack linksの数がいずれも等しい

elementary BSTに少し実装を加えるだけですべてのAPIを保ったまま効率化できる

木の調整

rotateLeft

何らかの理由でright leaning red linkが出来た場合は"回転"させる

right childをparentに昇格させり

parentをright childのleft childにする

right childのleft childをparentのright childにする

right childのcolorをblackにする

parentのcolorをredにする

rotateRight

left leaning red linkが2つ連続した場合は"回転"させる

flipColors

あるnodeの両方のlinksがredになった場合は"反転"させる

red childrenをblackにする

black parentをredにする

最終的に同じkeyを追加するなら順序に関係なくできあがるLLRB treeは同じ

keyの追加順がrandomでもdescendingでもascendingでも木の高さが最悪でも2lgNであることが保証される

off topic

なぜ赤黒なのか？

発明した当時Xeroxにいた

当時のXeroxでは多くのイノベーションが生み出されており、その中にレーザー印刷があった

レーザー印刷で美しく印刷できる色の中でも赤がひときわ他と見分けが付きやすい色だったので選んだ

赤黒木のまずい実装

電話会社が顧客情報を保存するデータベースのプロバイダーが検索と挿入に赤黒BSTを使って実装していた

赤黒木に関するオリジナルの論文では削除の実装が後ろの方にあったので多くの人は削除の実装を見てなかった

left-leaningに関する実装もなかった

データベースプロバイダーは赤黒BSTのバイナリ検索に通常のHibbard deletionを入れただけ

木の高さを常に一定に保つことが保証されている削除アルゴリズムではないが、バランスが取れていれば大丈夫と考えていた

そのシステムは木の高さが大きくなりすぎた場合に起動する複雑なエラー回復プロセスを持っていた

ツリー全体を再構築

削除の方法を変更したために、最終的には実装者が完全なアルゴリズムを使用していなかったために、クライアントがサービス停止を余儀なくされた

もし適切に実装されていれば、N個のキーを持つ木の高さはせいぜい2lgNだった

テレビ番組で赤黒木が何かのトリックに使われていたのを友人からのEメールで知った

赤黒木は連想配列や集合を構築するのに使われる

RubyのSortedSetではtbtreeがあれば使う、という実装になっている

B-Trees

平衡木を一般化したもの

1 nodeが持つkeyを2や3ではなく1000や4000にできる

たいていは1ページに収まる数を選ぶ

非常に浅い平衡木を作れる

大量のデータを扱いたいという背景

特に連続的なデータのブロックを扱う

1つのファイルだったり4096 bytes chunkだったり

ブロックをpageと呼ぶ

ローカルメモリではなく外部ストレージからページを読み込むコストが大きい

最小の探索数で到達し、キャッシュできればよい

B+ tree, B* treeといった改良種がある

Balanced treeの実用例

Red-black trees are widely used as system symbol tables.

Java: java.util.TreeMap, java.util.TreeSet.

C++ STL: map, multimap, multiset.

Linux kernel: completely fair scheduler, linux/rbtree.h.

Emacs: conservative stack scanning.

B-tree variants. B+ tree, B*tree, B# tree, …

B-trees (and variants) are widely used for file systems and databases.

Windows: NTFS.

Mac: HFS, HFS+.

Linux: ReiserFS, XFS, Ext3FS, JFS.

Databases: ORACLE, DB2, INGRES, SQL, PostgreSQL.

Geometric Applications of BSTs

平面上での点や長方形を扱う問題においてBSTが成功を収めている

1d Range Search

Database queryでよくあるrange search, range count

unordered array: insert = 1, range search, range count = linear time N

unordered array: insert = N, range search = R + logN, range count = logN

BST

Line segment intersection

線分が平面上に複数あるときに交差点がいくつあるか探す

sweep-line algorithm

y座標をkeyとするBSTを作る

horizontal lineの始点にぶつかったらBSTにそのlineのy座標をinsertする

horizontal lineの終点にぶつかったらBSTからそのlineのy座標をdeleteする

平面上での問題を扱うのにも木構造が使える

Assignment: KD-trees

Week 6

Hash Tables

Red Black BSTでlogarithmicは実現できたがそれより高速にできるか？できる

hashing

arrayにデータを格納する

keyからindexを高速に計算できればデータ量は関係ない

典型的なtime-space tradeoffへの対処

もし空間が無限なら雑なhash functionで構わない

もし時間が無限なら線形探索による雑な衝突回避で構わない

そうではないのでhashingが必要

hash function

$ index = f(key)

hashingの考え方自体は広く普及している

memory addressを用いるパターン

user defined classの場合は重要なfieldすべてのhashCodeからhashCodeを作る

Uniform hashing assumption

それぞれのkeyは0~M-1におおよそ均一にばらける

確率論で古くから研究されている

birthday problem

coupon collector

衝突の回避方法がいくつかある

Separate chaining symbol table

配列の要素にlistを持たせる

indexが衝突したらlistに追加する

Linear probing

open addressing

indexが衝突したらindex+1, +2, +3を見て空いているところに格納する

resizeが重要になってくる

半分はemptyであるようにする

現実世界の問題

Uniform hashing assumptionは通用する？

おおよそ。ただ航空力学や原子力制御やペースメーカーといったミッションクリティカルなシーンではRB BSTの利用を考える必要がある

脆弱なhash functionは攻撃対象になる

hash functionがわかればDOSで偏りを作ることができる

偏るとパフォーマンスが劣化する

Perl 5.8.0の連想配列, Linux 2.4.20のファイルシステムなどでも起きた

Separate chaining vs. linear probing

Separate chaining.

Easier to implement delete.

Performance degrades gracefully.

Clustering less sensitive to poorly-designed hash function.

Linear probing.

Less wasted space.

Better cache performance

派生形

Two-probe hashing (separate-chaining variant)

Double hashing (linear-probing variant)

Cuckoo hashing (linear-probing variant)

Hash tables vs. balanced search trees

Hash tables.

Simpler to code.

No effective alternative for unordered keys.

Faster for simple keys (a few arithmetic ops versus log N compares).

Better system support in Java for strings (e.g., cached hash code).

Balanced search trees.

Stronger performance guarantee.

Support for ordered ST operations.

Easier to implement compareTo() correctly than equals() and hashCode()

Set API

Exception filterとして機能する

spell checker: identify misspelled words

browser: mark visited pages

parental control: block sites

chess: detect draw

spam filter: eliminate spam

credit card: check for stolen cards

高速だがintersectionの処理時間はsmaller setの要素数に比例する

Dictionary

ordered operation (rank, range) を必要としない広範囲で活用可能

Indexing clients

file indexing

concordance (索引)

Symbol tableで実装できる

key = String, value = SET<Integer>

red black treeを使っている場合、sortされた状態にできる

Sparse vector

行列計算で疎な行列（0が多い）を扱う場合にsymbol tableが使える

sparce vectorは0以外の値を持つsymbol table